/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import org.jheaps.AddressableHeap
import java.lang.IllegalArgumentException
import java.math.BigInteger

/**
 * An addressable radix heap for [BigInteger] keys. The heap stores
 * [BigInteger] keys sorted according to the [ natural ordering][Comparable] of its keys. A radix heap is a monotone heap, especially
 * designed for algorithms (such as Dijkstra) which scan elements in order of
 * nondecreasing keys.
 *
 *
 *
 * The implementation use arrays in order to store the elements. Operations
 * `insert` and `findMin` are worst-case constant time. The cost of
 * operation `deleteMin` is amortized O(logC) assuming the radix-heap
 * contains keys in the range [0, C] or equivalently
 * [a,a+C].
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @author Dimitrios Michail
 *
 * @param <V>
 * the type of values maintained by this heap
 *
 * @see AddressableHeap
</V> */
class BigIntegerRadixAddressableHeap<V>(minKey: BigInteger, maxKey: BigInteger) : AbstractRadixAddressableHeap<BigInteger, V>() {
    /**
     * Constructs a new heap which can store values between a minimum and a
     * maximum key value (inclusive).
     *
     * It is important to use the smallest key range as the heap uses O(logC)
     * where C=maxKey-minKey+1 buckets to store elements. Moreover, the
     * operation `deleteMin` requires amortized O(logC) time.
     *
     * @param minKey
     * the non-negative minimum key that this heap supports
     * (inclusive)
     * @param maxKey
     * the maximum key that this heap supports (inclusive)
     * @throws IllegalArgumentException
     * if the minimum key is negative
     * @throws IllegalArgumentException
     * if the maximum key is less than the minimum key
     */
    init {
        if (minKey == null) {
            throw IllegalArgumentException("Minimum key cannot be null")
        }
        if (minKey < BigInteger.ZERO) {
            throw IllegalArgumentException("Minimum key must be non-negative")
        }
        this.minKey = minKey
        this.lastDeletedKey = minKey
        if (maxKey == null) {
            throw IllegalArgumentException("Maximum key cannot be null")
        }
        if (maxKey < minKey) {
            throw IllegalArgumentException("Maximum key cannot be less than the minimum")
        }
        this.maxKey = maxKey

        // compute number of buckets
        val diff: BigInteger = maxKey.subtract(minKey)
        val numBuckets: Int = 2 + 1 + diff.bitLength()

        // construct representation
        this.buckets = (java.lang.reflect.Array.newInstance(Node::class.java, numBuckets) as Array<Node?>?)!!
        this.size = 0
        this.currentMin = null
    }

    /**
     * {@inheritDoc}
     */
    override fun compare(o1: BigInteger, o2: BigInteger?): Int {
        return o1.compareTo(o2)
    }

    /**
     * {@inheritDoc}
     */
    override fun msd(a: BigInteger, b: BigInteger?): Int {
        if ((a == b)) {
            return -1
        }
        /*
         * return floor(log_2(a xor b)).
         */
        return a.xor(b).bitLength() - 1
    }


}
